//题目:
// 如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
// 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
// 给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int numberOfArithmeticSlices(vector<int>& nums) 
    {
        if(nums.size()<3)return 0;
        //1.创建dp表————dp[i].first表示以nums[i]为结尾的等差子数组个数，dp[i].second表示nums[i]与nums[i-1]的差值
        vector<pair<int,int>> dp(nums.size());
        //2.初始化
        dp[0].first=0,dp[0].second=0;
        dp[1].first=0,dp[1].second=nums[1]-nums[0];
        //3.填表————动态转移方程：dp[i].first=dp[i-1].first==0?
        for(int i=2;i<nums.size();i++)
        {
            dp[i].second=nums[i]-nums[i-1];
            if(dp[i-1].first==0)
            {
                if(dp[i-1].second==dp[i].second) dp[i].first=1;
                else dp[i].first=0;
            }
            else
            {
                if(dp[i-1].second==dp[i].second) dp[i].first=dp[i-1].first+1;
                else dp[i].first=0;
            }
        }
        //4.确定返回值
        int ret=0;
        for(int i=2;i<nums.size();i++)
            ret+=dp[i].first;
        return ret;
    }
};